/*
 Copyright (c) 2011 - 2016 The Regents of the University of
 California (Regents). All Rights Reserved.  Redistribution and use in
 source and binary forms, with or without modification, are permitted
 provided that the following conditions are met:

    * Redistributions of source code must retain the above
      copyright notice, this list of conditions and the following
      two paragraphs of disclaimer.
    * Redistributions in binary form must reproduce the above
      copyright notice, this list of conditions and the following
      two paragraphs of disclaimer in the documentation and/or other materials
      provided with the distribution.
    * Neither the name of the Regents nor the names of its contributors
      may be used to endorse or promote products derived from this
      software without specific prior written permission.

 IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT,
 SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS,
 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
 REGENTS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING DOCUMENTATION, IF
 ANY, PROVIDED HEREUNDER IS PROVIDED "AS IS". REGENTS HAS NO OBLIGATION
 TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
 MODIFICATIONS.
*/

import scala.collection.mutable.HashMap
import scala.collection.mutable.ArrayBuffer
import scala.util.matching.Regex
import scala.io.Source._
import java.io._

import TextComparator._
import VCDComparator._

object VCDComparator {
  val moduleDefRegex = """\$scope module (\S+) \$end""".r
  val signalDefRegex = """\$var wire (\d+) (\S+) (\S+) \$end""".r
  val signalValRegex = """b(\d+) (\S+)""".r
  val VCDSignalValueBase = 2

  /** Generate a signal name from a module name and a signal name
    * @param moduleName The name of the module containing the signal.
    * @param internalSignalName The name of the signal internal to the module.
    * @return The combined (unique) signal name.
    */
  def generateUniqueSignalName(moduleName: String, internalSignalName: String): String = "%s.%s".format(moduleName, internalSignalName)

  /** Return a map of short signal names to long (unique) signal names, and a list of module names.
    */
  def buildSignalDefs(si: Iterator[String]): Tuple2[Map[String, String], List[String]] = {
    val tSignalMap = scala.collection.mutable.HashMap[String, String]()
    val moduleNames = ArrayBuffer[String]()
    for (s <- si ) {
      s match {
        case moduleDefRegex(name) => moduleNames += name
        case signalDefRegex(width, rep, name) => tSignalMap.put(rep, generateUniqueSignalName(moduleNames.last, name))
        case _ => {}
      }
    }
    (tSignalMap.toMap, moduleNames.toList)
  }

  def compareFiles(masters: Array[String], tests: Array[String]): Option[ComparatorError] = {
    var finalResult: Option[ComparatorError] = None
    try {
      for ((masterFilePath, testFilePath) <- masters zip tests) {
        val masterFile = fromFile(masterFilePath)
        val masterLines = masterFile.getLines
        masterFile.close()
        val testFile = fromFile(testFilePath)
        val testLines = testFile.getLines
        testFile.close()
        val comparator = new VCDComparator(masterFilePath, testFilePath)
        val result = comparator.compare(masterLines.toIterator, testLines.toIterator)
        result match {
          case Some(e: ComparatorError) => throw e
          case _ => {}
        }
      }
    } catch {
      case e: ComparatorError => finalResult = Some(e)
    }
    finalResult
  }
}

class VCDComparator(masterPath: String, testPath: String) {
  type SignalStates = scala.collection.mutable.HashMap[String, Option[String]]

  /** Simulate the state of signals in a VCD file.
   *  Inspired by Palmer Dabbelt's vcddiff program.
   *  NOTE: This minimalist implementation is designed to deal with the VCD files generated by Chisel
   *   and may not work with generic VCD files.
   */
  case class VCDStateSim(lines: Iterator[String]) {
    // Partition the incoming stream into two sequences - definitions and data.
    val (defs, data) = lines.partition(_.startsWith("$"))
    // Generate the map from short signal names to long ones from the definition lines.
    val (shortToLong: Map[String, String], moduleNames: List[String]) = buildSignalDefs(defs)
    // Generate the inverse map.
    val longToShort = shortToLong.map(_.swap)
    // Create the signal state map, initialized to unknown signal values.
    // Use the long (original) signal names as the keys
    // Minor changes to the generated code could shuffle the short signal names
    //  and we want to compare values for the original (long) signals
    val signalStates: SignalStates = shortToLong.values.map(k => (k, None))(collection.breakOut)
    var clockTick = -1
    // Is there more data to be checked?
    def hasNext: Boolean = data.hasNext

    /** Step one cycle.
      *  Read data lines updating the signal state until we see a clock change.
      */
    def step() {
      val startingTick = clockTick
      // Loop while we have hasNext data and we haven't changed the clock
      while (hasNext && clockTick == startingTick) {
        val line = data.next()
        // Is this a clock tick or a signal change?
        line(0) match {
          case '#' => {
            // Increment the clock. This should terminate the loop.
            clockTick += 1
          }
          case 'b' => {
            // Extract the signal name (short) and new value and update the signal state map for the original (long) named signal.
            line match {
              case signalValRegex(value, shortName) => signalStates(shortToLong(shortName)) = Some(value)
              case _ => throw new ComparatorError("unrecognized line '%s'".format(line))
            }
          }
        }
      }
    }

    /** Position the stream to the cycle where the specified signal has the specified value.
      *  NOTE: This assumes we need to perform at least one step (i.e., the terminating condition is not current).
      *  @param name The name of the signal.
      *  @param value The desired signal value.
      */
    def seek(longName: String, value: BigInt) {
      do {
        // If we've hit the end of the stream, indicate failure.
        if (!hasNext) {
          throw new ComparatorError("can't find %s with value %d.".format(longName, value))
        }
        step()
      } while (BigInt(signalStates(longName).get, VCDSignalValueBase) != value)
    }

    /** Read and update the signal states until we see reset de-asserted.
      *
      */
    def init() {
      step()  // Position to the start of the first cycle.
      // Find the reset signal
      val reset = generateUniqueSignalName(moduleNames.head, "reset")
      if (signalStates.contains(reset)) {
        seek(reset, 0)
      }
    }

    /** Do two simulations have the same signal state?
      * @param that The other simulation state to compare
      * @return True if both simulations have identical signal states.
      */
    def sameSignalValues(that: VCDStateSim): Boolean = {
      this.signalStates equals that.signalStates
    }
  }

  /** Compare two VCD file streams.
    *  @param masterLines An iterator for the master (reference) VCD file.
    *  @param testLines An iterator for the comparison file.
    *  @return A ComparatorError if the files differ, otherwise None.
    */
  def compare(masterLines: Iterator[String], testLines: Iterator[String]): Option[ComparatorError] = {
    var result: Option[ComparatorError] = None
    val vcdStates = new HashMap[String, VCDStateSim]
    try {
      // Initialize and position the two streams
      for ( (name, stream) <- List(("master", masterLines), ("test", testLines))) {
        val sim = new VCDStateSim(stream)
        vcdStates(name) = sim
        sim.init()
      }
      // Verify both define the same set of signals.
      val differentSignals = vcdStates("master").signalStates.keySet &~ vcdStates("test").signalStates.keySet
      if (!differentSignals.isEmpty) {
        throw new ComparatorError("master and test differ on %s".format(differentSignals.mkString(", ")))
      }

      // Step through the files ensuring signals are the same at each cycle, stopping when both files contain no hasNext data.
      do {
        if (!(vcdStates("master") sameSignalValues vcdStates("test"))) {
          val clockTick = vcdStates("master").clockTick
          val signals = vcdStates("master").signalStates.filter{ case (k, v) => vcdStates("test").signalStates(k) != v }.keys.mkString(", ")
          throw new ComparatorError("%s and %s differ for signal %s at clockTick %d".format(masterPath, testPath, signals, clockTick))
        }
        vcdStates("master").step()
        vcdStates("test").step()
      } while (vcdStates("master").hasNext || vcdStates("test").hasNext)
    } catch {
      case e: ComparatorError => result = Some(e)
    }
    result
  }
}
